package leetcode.tree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

/**
 * 给你 root1 和 root2 这两棵二叉搜索树。
 *
 * 请你返回一个列表，其中包含 两棵树 中的所有整数并按 升序 排序。.
 *
 *  
 *
 * 示例 1：
 *
 *
 *
 * 输入：root1 = [2,1,4], root2 = [1,0,3]
 * 输出：[0,1,1,2,3,4]
 * 示例 2：
 *
 * 输入：root1 = [0,-10,10], root2 = [5,1,7,0,2]
 * 输出：[-10,0,0,1,2,5,7,10]
 * 示例 3：
 *
 * 输入：root1 = [], root2 = [5,1,7,0,2]
 * 输出：[0,1,2,5,7]
 * 示例 4：
 *
 * 输入：root1 = [0,-10,10], root2 = []
 * 输出：[-10,0,10]
 * 示例 5：
 *
 *
 *
 * 输入：root1 = [1,null,8], root2 = [8,1]
 * 输出：[1,1,8,8]
 *  
 *
 * 提示：
 *
 * 每棵树最多有 5000 个节点。
 * 每个节点的值在 [-10^5, 10^5] 之间。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/all-elements-in-two-binary-search-trees
 */
public class 两棵二叉搜索树中的所有元素 {

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    private static void getVal(TreeNode t, List<Integer> l){
        if (t != null){
            l.add(t.val);
            getVal(t.left, l);
            getVal(t.right, l);
        }
    }

    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> lr = new ArrayList<>();
        getVal(root1, lr);
        getVal(root2, lr);
        Integer[] r = new Integer[lr.size()];
        lr.toArray(r);
        Arrays.sort(r, (o1, o2) -> o1 - o2);
        List<Integer> llr = new ArrayList<>(r.length);
        llr.addAll(Arrays.asList(r));
        return llr;
    }

    private static void getVal_1(TreeNode t, PriorityQueue<Integer> l){
        if (t != null){
            l.offer(t.val);
            getVal_1(t.left, l);
            getVal_1(t.right, l);
        }
    }

    public List<Integer> getAllElements_1(TreeNode root1, TreeNode root2) {
        PriorityQueue<Integer> lr = new PriorityQueue<>((o1, o2)->o1-o2);
        getVal_1(root1, lr);
        getVal_1(root2, lr);
        List<Integer> llr = new ArrayList<>(lr.size());
        Integer i = lr.poll();
        while (i != null){
            llr.add(i);
            i = lr.poll();
        }
        return llr;
    }
}
